#include "../include/StringMatch.h"

int StringMatch::simpleMatch(const string& s, const string& t) {
    int i = 0, j = 0;
    int s_len = s.length();
    int t_len = t.length();
    
    while (i < s_len && j < t_len) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    
    if (j == t_len) {
        return i - j;
    } else {
        return -1;
    }
}

vector<int> StringMatch::getNext(const string& t) {
    int t_len = t.length();
    vector<int> next(t_len, 0);
    int j = 0, k = -1;
    next[0] = -1;
    
    while (j < t_len - 1) {
        if (k == -1 || t[j] == t[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

vector<int> StringMatch::getNextVal(const string& t) {
    int t_len = t.length();
    vector<int> nextVal(t_len, 0);
    int j = 0, k = -1;
    nextVal[0] = -1;
    
    while (j < t_len - 1) {
        if (k == -1 || t[j] == t[k]) {
            j++;
            k++;
            if (t[j] != t[k]) {
                nextVal[j] = k;
            } else {
                nextVal[j] = nextVal[k];
            }
        } else {
            k = nextVal[k];
        }
    }
    return nextVal;
}

int StringMatch::kmpMatch(const string& s, const string& t) {
    vector<int> nextVal = getNextVal(t);
    int i = 0, j = 0;
    int s_len = s.length();
    int t_len = t.length();
    
    while (i < s_len && j < t_len) {
        if (j == -1 || s[i] == t[j]) {
            i++;
            j++;
        } else {
            j = nextVal[j];
        }
    }
    
    if (j == t_len) {
        return i - j;
    } else {
        return -1;
    }
}

void StringMatch::testStringMatching() {
    cout << "=== 字符串匹配测试 ===" << endl;
    
    string s = "abcabcdbacaedbcdfebacdefg";
    string t = "bacaedbcdfeba";
    
    cout << "目标串 s: " << s << endl;
    cout << "模式串 t: " << t << endl;
    
    int pos1 = simpleMatch(s, t);
    cout << "简单匹配算法位置: " << pos1 << endl;
    
    int pos2 = kmpMatch(s, t);
    cout << "KMP算法位置: " << pos2 << endl;
    
    cout << endl;
}

void StringMatch::interactiveTest() {
    cout << "=== 字符串匹配交互式测试 ===" << endl;
    
    while (true) {
        cout << "\n请选择操作：" << endl;
        cout << "1. 输入新的字符串进行匹配" << endl;
        cout << "2. 使用默认示例" << endl;
        cout << "0. 返回主菜单" << endl;

        int choice = Utils::getIntInput("请输入选择 (0-2): ");

        if (choice == 0) break;

        string s, t;
        
        if (choice == 1) {
            s = Utils::getStringInput("请输入目标串 s: ");
            t = Utils::getStringInput("请输入模式串 t: ");
        } else if (choice == 2) {
            s = "abcabcdbacaedbcdfebacdefg";
            t = "bacaedbcdfeba";
            cout << "使用默认示例：" << endl;
            cout << "目标串 s: " << s << endl;
            cout << "模式串 t: " << t << endl;
        } else {
            cout << "无效选择！" << endl;
            continue;
        }
        
        if (s.empty() || t.empty()) {
            cout << "错误：字符串不能为空！" << endl;
            continue;
        }
        
        cout << "\n匹配结果：" << endl;
        int pos1 = simpleMatch(s, t);
        cout << "简单匹配算法位置: " << (pos1 >= 0 ? to_string(pos1) : "未找到") << endl;
        
        int pos2 = kmpMatch(s, t);
        cout << "KMP算法位置: " << (pos2 >= 0 ? to_string(pos2) : "未找到") << endl;
        
        if (pos1 >= 0) {
            cout << "匹配到的子串: " << s.substr(pos1, t.length()) << endl;
        }
    }
}